package com.demo.java.OD351_400.OD362;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【购物(B卷)】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/146223162
 */
public class OdMain {

    // 创建一个名为 "Item" 的类，用于存储三个整数值：总和（total），索引（idx），和下一个值（next）
    static class Item {
        int total;
        int idx;
        int next;

        public Item(int a, int b, int c) {
            total = a;
            idx = b;
            next = c;
        }
    }

    // 创建一个名为 "CompareItems" 的比较器类，用于比较 "Item" 对象的 "next" 属性
    static class CompareItems implements Comparator<Item> {
        @Override
        public int compare(Item a, Item b) {
            return Integer.compare(a.next, b.next);
        }
    }

    public static void main(String[] args) throws IOException {
        // 从标准输入中读取数据
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 读取第一行的输入，包含两整数：num（数量）和 maxCount（最大计数）
        StringTokenizer st = new StringTokenizer(br.readLine());
        int num = Integer.parseInt(st.nextToken());
        int maxCount = Integer.parseInt(st.nextToken());

        // 读取第二行的输入，包含 num 个整数值，并将它们存储在 "values" 列表中
        st = new StringTokenizer(br.readLine());
        List<Integer> values = new ArrayList<>();
        for (int i = 0; i < num; i++) {
            values.add(Integer.parseInt(st.nextToken()));
        }

        // 对 "values" 列表进行排序
        Collections.sort(values);

        // 创建一个优先队列 "pq"，用于存储 "Item" 对象，并使用 "CompareItems" 比较器进行排序
        PriorityQueue<Item> pq = new PriorityQueue<>(new CompareItems());

        // 向 "pq" 添加初始的 "Item" 对象，表示从未选取任何元素的情况
        pq.add(new Item(0, 0, values.get(0)));

        // 当 "pq" 不为空且 maxCount 大于 0 时，进行循环
        while (!pq.isEmpty() && maxCount > 0) {
            // 从 "pq" 中弹出当前 "Item" 对象
            Item current = pq.poll();

            // 打印当前的 "next" 值
            System.out.println(current.next);

            // 减少 maxCount 计数
            maxCount--;

            // 如果仍然有未处理的元素（索引小于 num - 1），则将它们添加到 "pq" 中
            if (current.idx < num - 1) {
                pq.add(new Item(current.total, current.idx + 1,
                        current.total + values.get(current.idx + 1)));
                pq.add(new Item(current.next, current.idx + 1,
                        current.next + values.get(current.idx + 1)));
            }
        }
    }
}